package LearnDataStructure.c_树结构.有序树.二叉树;

import LearnDataStructure.c_树结构.BSTNode;
import LearnDataStructure.c_树结构.MyBinarySearchTreeAPI;

import java.util.*;
import java.util.function.Consumer;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-07 18:39
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.c_树结构.有序树.二叉树
 */
/*

log M   除以  log N
   e            e

等于

log M
   N


Math.log(x)
返回x以e为底的对数，返回数值的类型是double。
Math.floor(x)
向上取整的四舍五入，Math.floor(5.1) = 6


int x = 1 << y
x代表2^y


满二叉树，设根节点算第1层
那么从root到第n层，总共的节点个数是(2^n - 1)个
4层满二叉树的节点是2^4 - 1 = 15个

对于完全二叉树，假设我们利用m个节点制作成满二叉树，最终结果会有

(log m)(对这个对数进行向下取整) + 1   层
(   2 )

log 15 = 3.9.... 即3 + 1 = 4层
   2
 */
public class b_MyBinaryTreebyLinked<K,V> implements MyBinarySearchTreeAPI<K,V> {
    private BSTNode<K,V> root = null;   //根节点
    public int size;                   //当前容器元素个数
    private Comparator<K> comparator;   //比较器

    public b_MyBinaryTreebyLinked(Comparator<K> comparator) {
        this.comparator = comparator;
    }

    public b_MyBinaryTreebyLinked() {
    }

    public void setRoot(BSTNode<K, V> root) {
        this.root = root;
    }

    public BSTNode<K, V> getRoot() {
        return root;
    }

    /**
     * 添加元素
     * @param key
     * @param value
     * @return
     */
    @Override
    public BSTNode<K, V> insert(K key, V value) {
        /*
        严格来说 instanceof 是 Java 中的一个双目运算符，由于它是由字母组成的，所以也是 Java 的保留关键字。
        在 Java 中可以使用 instanceof 关键字判断一个对象是否为一个类（或接口、抽象类、父类）的实例，语法格式如下所示。
        boolean result = obj instanceof Class
        其中，obj 是一个对象，Class 表示一个类或接口。obj 是 class 类（或接口）的实例或者子类实例时，结果 result 返回 true，否则返回 false。
         */
        if (!(key instanceof Comparable)) {//判断key能否进行比较操作
            throw new ClassCastException();
        }
        BSTNode<K,V> p = null;
        BSTNode<K,V> current = root;        //从根节点开始比较
        while (current != null) {
            p = current;                    //从根节点开始比较
            if (compare(key,current.key) < 0) {
                current = current.left;     //左孩子方向继续走
            } else if (compare(key,current.key) > 0) {
                current = current.right;    //右孩子方向继续走
            } else {                        //相等，即这个key已存在二叉树中
                current.value = value;      //做一次value的替换,因为即便key相同，新value与树中的value也不一定相同
                return current;//走到这，插入完成了，直接返回就行了
            }
        }
        /*
        只要走出了这个循环，就代表
        p的某一个孩子，是current
        而且这个current是null
         */
        current = new BSTNode<K,V>(key,value,null,null,null);//所以这里对current赋值
        current.parent = p;//在current视角，确认p与current的关系
        boolean needUpdateHeight = false;
        if (p == null) {//如果这个二叉树是空的，那么p其实就是null；这个判断分支只会在一开始构造二叉树的时候才会执行
            root = current;//所以这句相当于给这个空二叉树放入根节点
            needUpdateHeight = true;
        } else if (compare(key,p.key) < 0) {
            p.left = current;//在p视角，确认p与current的关系
            current.isLeftChild = true;//current标记自己的定位
            if (p.right == null) {
                needUpdateHeight = true;
            }
        } else {//compare(key,p.key) > 0;不可能会有等于的情况；因为如果存在等于，在上面已经return current;
            p.right = current;//同理
            current.isLeftChild = false;//同理
            if (p.left == null) {
                needUpdateHeight = true;
            }
        }

        size++;
        if (needUpdateHeight) {//只有满足“在叶子节点新增，新的节点”，才进行树高更新；但实际上只要新增节点的key是不存在二叉数中的，就必定会触发这个if
            updateHeight(current);
        }
        return current;
    }

    @SuppressWarnings({"unchecked", "rawtypes"})
    private int compare(K source, K other) {
        if (comparator == null) {
            return ((Comparable) source).compareTo((Comparable) other);
        } else {
            return comparator.compare(source,other);
        }
    }

    /**
     * 更新当前节点为根节点的子树的高度
     * 以current为最底层节点，向上寻脉
     * 以递归的方式
     * @param current
     */
    private void updateHeight(BSTNode<K,V> current) {
        if (current.parent == null) {//递归出口，即root没有父节点
            return;
        }
        BSTNode<K,V> node = current.parent;
        if (node.height == current.height) {
            node.height++;
            updateHeight(node);
        }
    }

    @Override
    public void remove(K key) {
        BSTNode<K, V> node = getValue(key);
        removeNode(node);
        size--;
    }

    public void removeNode(BSTNode<K,V> node) {
        if (node != null) {
            if (node.left == null && node.right == null) {                  //情况1，叶子节点
                if (node.parent == null) {//情况1的特殊情况：node是root
                    root = null;
                    return;
                }
                if (node.isLeftChild) {//情况1的普通情况1：是左孩子
                    node.parent.left = null;
                } else {//情况1的普通情况2：是右孩子
                    node.parent.right = null;
                }
                //无论上述哪种情况，node都要赋值为空；
                // node.parent = null;
                node = null;
            } else if (node.left == null) {                                 //情况2，单子节点，node仅有右孩子
                if (node.isLeftChild) {//情况2的普通情况1：node是左孩子
                    BSTNode<K, V> rightOfNode = node.right;
                    BSTNode<K, V> parentOfNode = node.parent;
                    parentOfNode.left = rightOfNode;
                    rightOfNode.parent = parentOfNode;
                } else if (node.isRight()) {//情况2的普通情况2：node是右孩子
                    BSTNode<K, V> rightOfNode = node.right;
                    BSTNode<K, V> parentOfNode = node.parent;
                    parentOfNode.right = rightOfNode;
                    rightOfNode.parent = parentOfNode;
                } else {//情况2的特殊情况：node是root
                    root = node.right;
                }
                // node.parent = null;
                node = null;
            } else if (node.right == null) {                                //情况3，单子节点，node仅有左孩子
                if (node.isLeftChild) {//情况3的普通情况1：node是左孩子
                    BSTNode<K, V> leftOfNode = node.left;
                    BSTNode<K, V> parentOfNode = node.parent;
                    parentOfNode.left = leftOfNode;
                    leftOfNode.parent = parentOfNode;
                } else if (node.isRight()) {//情况3的普通情况2：node是右孩子
                    BSTNode<K, V> leftOfNode = node.left;
                    BSTNode<K, V> parentOfNode = node.parent;
                    parentOfNode.right = leftOfNode;
                    leftOfNode.parent = parentOfNode;
                } else {//情况3的特殊情况：node是root
                    root = node.left;
                }
                node = null;
            } else {                                                        //情况4，双子节点，node有左右孩子
                BSTNode<K, V> minOfRightOfNode = min(node.right);
                node.key = minOfRightOfNode.key;
                node.value = minOfRightOfNode.value;
                removeNode(minOfRightOfNode);//minOfRightOfNode是叶子节点或者“自身是左孩子但是仅有右孩子”节点
            }
        }
    }

    /**
     * 最好O(logN)
     * 最坏O(N)
     * @param key
     * @return
     */
    @Override
    public BSTNode<K,V> getValue(K key) {
        BSTNode<K,V> current = root;
        while (current != null && compare(current.key,key) != 0) {
            if (compare(current.key,key) < 0) {
                current = current.right;
            } else {
                current = current.left;
            }
        }
        /*
        跳出循环有两种可能
        1.compare(current.key,key) == 0 就是找到了
        2.current == null 就是没找到
         */
        return current;
    }

    @Override
    public K predecessor(K key) {
        BSTNode<K,V> node = getValue(key);
        if (node == null) {
            return null;
        }
        if (node.left != null) {
            return max(node.left).key;
        }
        BSTNode<K,V> p = node.parent;
        while (p != null && node.isLeftChild) {
            node = p;//node指针顺着树上移
            p = p.parent;//p指针顺着树上移
        }
        /*
        跳出循环2种情况
        p == null，即没有满足的前驱节点
        找到了前驱节点，就是p
         */
        return p == null ? null : p.key;
    }

    @Override
    public K successor(K key) {
        BSTNode<K, V> node = getValue(key);
        if (node == null) {
            return null;
        }
        if (node.right != null){
            return min(node.right).key;
        }
        BSTNode<K, V> p = node.parent;
        while (p != null && node.isRight()) {
            node = p;
            p = p.parent;
        }
        return p == null ? null : p.key;
    }

    @Override
    public K min() {
        BSTNode<K,V> current = root;
        while (current.left != null) {
            current = current.left;
        }
        return current.key;
    }

    public BSTNode<K, V> min(BSTNode<K, V> node) {
        BSTNode<K, V> current = node;
        while (current.left != null) {
            current = current.left;
        }
        return current;
    }

    @Override
    public K max() {
        BSTNode<K,V> current = root;
        while (current.right != null) {
            current = current.right;
        }
        return current.key;
    }

    public BSTNode<K, V> max(BSTNode<K, V> node) {
        BSTNode<K,V> current = node;
        while (current.right != null) {
            current = current.right;
        }
        return current;
    }

    @Override
    public int getSize() {
        return size;
    }

    /**
     * 返回严格意义上的树高
     * 作用对整棵树
     * @return
     */
    @Override
    public int getHeight() {
        return getHeight(root) - 1;
    }

    /**
     * 返回能用于toString方法的树高
     * 返回能用于平衡旋转方法的树高
     * 以参数为节点的子树
     * @param root
     * @return
     */
    public int getHeight(BSTNode<K, V> root) {
        if (root == null) {
            return 0;
        } else {
            int leftTreeHeight = getHeight(root.left);
            int rightTreeHeight = getHeight(root.right);
            return 1 + Math.max(leftTreeHeight,rightTreeHeight);
        }
    }

    /**
     * 中序遍历全树
     * @return
     */
    public List<BSTNode<K, V>> inOrder() {
        List<BSTNode<K, V>> result = new ArrayList<BSTNode<K, V>>();
        inOrder(root,result);
        return result;
    }

    /**
     * 中序遍历以node为根节点的子树，递归形式
     * 左中右
     * @param node list
     * @param list
     */
    @Override
    public void inOrder(BSTNode<K, V> node, List<BSTNode<K, V>> list) {
        if (node.left == null && node.right == null) {
            list.add(node);
        } else {
            if (node.left != null) {
                inOrder(node.left, list);
            }
            list.add(node);
            if (node.right != null) {
                inOrder(node.right, list);
            }
        }
    }

    public List<BSTNode<K, V>> inOrderIteration() {
        List<BSTNode<K, V>> result = new ArrayList<BSTNode<K, V>>();
        inOrderIteration(root,result);
        return result;
    }

    /**
     * 中序遍历以node为根节点的子树，迭代形式
     * 左中右
     * @param node
     * @param list
     */
    public void inOrderIteration(BSTNode<K, V> node, List<BSTNode<K, V>> list) {
        Stack<BSTNode<K, V>> stack = new Stack<BSTNode<K, V>>();
        BSTNode<K, V> current = node;
        //curr不为空或者栈不为空，都可以继续处理
        while (current != null || !stack.isEmpty()) {//没有生产也没有消费，就退出这个while
            //沿左支线一撸到底，全部入栈
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            //处理栈顶，相当于弹出
            if (!stack.isEmpty()) {
                BSTNode<K, V> popElement = stack.pop();
                list.add(popElement);
                /*
                curr指向pop的右子树，目的是继续外层循环
                当然popElement.right有可能为空
                为空，只消费栈中内容，相当于“中序遍历中，输出当前子树的根节点的操作”
                不为空，就要向栈中生产若干内容，相当于“中序遍历中，输出当前子树的右子树的操作”
                 */
                current = popElement.right;
            }
        }
    }

    /**
     * 前序遍历全树
     * @return
     */
    public void preOrder() {

    }

    /**
     * 前序遍历以node为根节点的子树
     * 中左右
     * @param node list
     * @param list
     */
    public void preOrder(BSTNode<K, V> node, List<BSTNode<K, V>> list) {

    }

    /**
     * 后序遍历全树
     * @return
     */
    public void postOrder() {

    }

    /**
     * 后序遍历以node为根节点的子树
     * 左右中
     * @param node list
     * @param list
     */
    public void postOrder(BSTNode<K, V> node, List<BSTNode<K, V>> list) {

    }

    /**
     * 层级遍历全树,同时给该层每个节点打上正确num
     * @return
     */
    @Override
    public List<List<BSTNode<K, V>>> levelOrder() {
        root.num = 1;
        return levelOrder(root);
    }

    public List<List<BSTNode<K, V>>> levelOrder(BSTNode<K, V> root) {
        List<List<BSTNode<K, V>>> result = new ArrayList<List<BSTNode<K, V>>>();
        Queue<BSTNode<K, V>> queue = new LinkedList<BSTNode<K, V>>();
        //初始化
        queue.add(root);
        BSTNode<K, V> last = root;
        BSTNode<K, V> next = null;

        //一定有第一行;为第一行做准备
        List<BSTNode<K, V>> currentLine = new ArrayList<BSTNode<K, V>>();
        result.add(currentLine);

        while (!queue.isEmpty()) {
            BSTNode<K, V> peek = queue.peek();//peek是待出列元素
            if (peek.left != null) {
                peek.left.num = peek.num * 2;
                queue.add(peek.left);
                next = peek.left;//移动指针；最终next会指向最后一个孩子
            }
            if (peek.right != null) {
                peek.right.num = peek.num * 2 + 1;
                queue.add(peek.right);
                next = peek.right;//移动指针；最终next会指向最后一个孩子
            }
            //队列弹出首元素;代表当前的行的列表currentLine,此时添加出列的元素
            currentLine.add(queue.poll());
            //如果弹出元素就是last指针指向的元素，且队列不为空
            if (peek == last && !queue.isEmpty()) {
                currentLine = new ArrayList<BSTNode<K, V>>();
                result.add(currentLine);
                last = next;
            }
        }
        return result;
    }

    @Override
    public String toString() {
        StringBuilder result = new StringBuilder();
        List<List<BSTNode<K, V>>> lists = levelOrder();
        int level = 1;
        int height = getHeight() + 1;
        for (List<BSTNode<K, V>> list : lists) {
            int gap = ex(2,height - level) - 1;
            int beginNum = ex(2, level - 1);
            for (BSTNode<K, V> node : list) {
                while (beginNum != node.num) {
                    for (int i = 0; i < 2 * gap; i++) {
                        result.append(" ");
                    }
                    result.append("**");

                    for (int i = 0; i < 2 * gap; i++) {
                        result.append(" ");
                    }
                    result.append("  ");
                    beginNum++;
                }

                for (int i = 0; i < 2 * gap; i++) {
                    result.append(" ");
                }
                result.append(node.key);

                for (int i = 0; i < 2 * gap; i++) {
                    result.append(" ");
                }
                result.append("  ");
                beginNum++;
            }
            level++;
            result.append("\n");
        }
        return result.toString();
    }

    /**
     * 返回a^n
     * 快速幂运算
     * @param a
     * @param n
     * @return
     */
    public int ex(int a, int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return a;
        }
        int temp = a;//代表a的1次方
        int result = 1;//返回结果
        int exponent = 1;//当前已经实现的幂的数值
        while ((exponent << 1) < n) {
            temp = temp * temp;
            exponent = exponent << 1;
        }
        result = result * ex(a, n - exponent);
        return result * temp;
    }

    /**
     * 查看当前整个树是否平衡
     * @return
     */
    @Override
    public boolean isBalance() {
        return !unBalance(root);
    }

    /**
     * 查看当前节点为根节点的子树是否平衡
     * @param node
     * @return
     */
    public boolean unBalance(BSTNode<K,V> node) {
        if (node == null) {
            return false;
        }
        int difference = getHeight(node.left) - getHeight(node.right);
        if (Math.abs(difference) > 1 || unBalance(node.left) || unBalance(node.right)) {
            return true;
        }
        return false;
    }

    /**
     * 左旋操作
     * @param p
     * @param q
     */
    public void leftRotate(BSTNode<K, V> p, BSTNode<K, V> q) {
        boolean pState = p.isLeft();
        BSTNode<K, V> parentOfP = p.parent;
        BSTNode<K, V> leftOfQ = q.left;

        //更新p的右孩子
        p.right = leftOfQ;

        //存在这个节点
        if (leftOfQ != null) {
            leftOfQ.parent = p;//认父
            leftOfQ.isLeftChild = false;//因为当前在新父节点上是右孩子
        }

        //开始对p进行认父；也就是把p和q的关系重新定义
        q.left = p;
        p.parent = q;
        p.isLeftChild = true;//因为当前在新父节点上是左孩子

        //开始对q进行认父；也就是把q和parentOfP的关系重新定义；下面的所有代码都是“认父”操作
        q.parent = parentOfP;
        if (parentOfP == null) {//特殊情况判断，也就是p是根节点
            setRoot(q);//把q设成这棵树的root
            return;
        }
        if (pState) {//判断p一开始的时候是什么孩子；下面就针对性的更改
            parentOfP.left = q;
            q.isLeftChild = true;
        } else {
            parentOfP.right = q;
            q.isLeftChild = false;
        }
    }

    /**
     * 右旋操作
     * @param p
     * @param q
     */
    public void rightRotate(BSTNode<K, V> p, BSTNode<K, V> q) {
        boolean pState = p.isLeftChild;
        BSTNode<K, V> parentOfP = p.parent;
        BSTNode<K, V> rightOfQ = q.right;

        p.left = rightOfQ;
        if (rightOfQ != null) {
            rightOfQ.parent = p;
            rightOfQ.isLeftChild = true;
        }

        q.right = p;
        p.parent = q;
        p.isLeftChild = false;

        q.parent = parentOfP;
        if (parentOfP == null) {
            setRoot(q);
            return;
        }
        if (pState) {
            parentOfP.left = q;
            q.isLeftChild = true;
        } else {
            parentOfP.right = q;
            q.isLeftChild = false;
        }
    }

    /**
     * 返回整棵树的所有叶子节点个数
     * @return
     */
    public int getLeafNodeNums() {
        return getLeafNodeNums(root);
    }

    public int getLeafNodeNums(BSTNode<K, V> node) {
        if (node == null) {
            return 0;
        }
        if (node.left == null && node.right == null) {
            return 1;
        }
        int num = 0;
        num = getLeafNodeNums(node.left) + getLeafNodeNums(node.right);
        return num;
    }

    /**
     * 返回第K层的节点个数
     * @return
     */
     public int getNodeNumsOfKlevel(int k) {
         int result = levelOrder().get(k - 1).size();
         return result;
    }

    /**
     * 返回这棵树是否是完全二叉树
     * @return
     */
    public boolean isFullBinaryTree() {
        List<List<BSTNode<K, V>>> lists = levelOrder();
        int totalLayers = lists.size();
        for (int currentLayer = 0; currentLayer < totalLayers; currentLayer++) {
            List<BSTNode<K, V>> currentLine = lists.get(currentLayer);
            int currentLineNums = currentLine.size();
            if (currentLineNums != (int)Math.pow(2,currentLayer) && currentLayer != totalLayers - 1) {
                /*
                如果当前层currentLayer的所有节点个数currentLineNums不符合“完全填满时这层本该有的数量Math.pow(2,currentLayer)”
                同时当前层currentLayer不是整棵树的最后一层
                就代表着这棵树在中间的某一层存在“未填满”
                */
                return false;
            } else if (currentLayer == totalLayers - 1) {
                /*
                如果当前层currentLayer是整棵树的最后一层
                num                                 代表该节点的实际的“第几号”
                Math.pow(2,currentLayer) + index    代表该节点的理论的“第几号”
                 */
                for (int index = 0; index < currentLineNums; index++) {//对最后一层每一个元素遍历
                    BSTNode<K, V> node = currentLine.get(index);
                    if (node.num != (int)Math.pow(2,currentLayer) + index) {//理论与实际冲突，代表最后一层存在“未填满”
                        return false;
                    }
                }
            }
        }
        return true;
    }

    /**
     * 返回this与参数otherTree是否相同
     * @return
     */
    public boolean isSameTree(BSTNode<K,V> otherTree) {
        return false;
    }

    /**
     * 返回this与参数otherTree是否镜像
     * @return
     */
    public boolean isMirrorTree(BSTNode<K,V> otherTree) {
        return false;
    }

    /**
     * 水平翻转二叉树；也就是左右翻转，需要递归
     */
    public void flipHorizontalTree() {

    }

    /**
     * 范围搜索二叉树
     * @param key1
     * @param key2
     * @return
     */
    public List<BSTNode<K,V>> areaSearch(K key1, K key2) {
        List<BSTNode<K,V>> result = new ArrayList<BSTNode<K,V>>();
        areaSearch(root, key1, key2, result);
        return result;
    }

    public void areaSearch(BSTNode<K,V> node, K key1, K key2, List<BSTNode<K,V>> list) {
        if (node == null) {
            return;
        }
        K key = node.key;
        if (compare(key,key1) > 0) {//key > key1
            areaSearch(node.left, key1, key2, list);//递归地寻找这棵树中，最接近范围的左边缘(key1)的节点
        }
        if (compare(key,key1) >= 0 && compare(key,key2) <= 0) {//符合范围，就添加当前node
            list.add(node);
        }
        if (compare(key,key2) < 0) {//key < key2
            areaSearch(node.right, key1, key2, list);//递归地寻找这棵树中，最接近范围的右边缘(key2)的节点
        }
    }
}

